COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	                          Math/CIS 280 exam
C00006 00003	****************
C00011 00004	**************
C00014 ENDMK
C⊗;
                          Math/CIS 280 exam

Take-home exam; due in one week (March 18, 1975).  You may use any (other) in-animate
objects to help do this exam. Collusion is not allowed.  WARNING: Go through the exam
before Thursday!  Thursday  I will answer  questions about the exam.  If you wait  to
Monday night to start work on the exam YOU WILL LOSE. 

Note: due to jury duty screw-up there will only be two exams, not three.


write the following functions or predicates 

dellst[u]         6 points
For the list u, dellst return a list of the atomic elements of u.
Examples:
	dellst[(A B C)] = (A B C)
	dellst[(A (B C) D (E))] = (A D)

Write dellst two ways: with and without a use of functional arguments.


vectoradd[u;v]    3 points
For lists u and v (assumed to be of equal length) this function this function returns
a list, each element of which is the sum of the corresponding elements in u and v. 
You may use plus[x;y] <= x+y; do with and without functional arguments.
Examples:
	vectoradd[(5 3);(2 -4)] = (7 -1)


allthesame[u]     3 points
For the  list u,  allthesame returns  T if  and only  if all  the elements  of u  are
identical. 


setdif[u;v]       3 points
For the lists, u and v, setdif returns a list consisting of all elements contained in
u and not contained in v. 
Examples:
	setdif[(5 4);()] = (5 4)
	setdif[(X 4 Y); (2 3 4)] = (X Y)
	setdif[(A B);(B C A D)] = ().

******************
Modifying the evaluator:   10 points
We have been using λ-notation as a binding mechanism for call-by-value.  We have aslo
noticed that it would  be convenient to have arguments passed into a function body in
unevaluated form (special forms, for  example).  We propose  to add a new binder,  β,
which  will be  used  in contexts  like  the  λ-notation but  the  arguments are  NOT
evaluated before they are passed into the body of the β-expression. 

Show what modifications would have to be made to our current evaluation scheme.

For example: Given, foo <=λ[x]car[x]  evaluation of foo[cons[A;B]] would give A.
What would 
   baz <= β[[x;y]cons[x;y]] give as evaluation for baz[car[A];cdr[b]]?

HINT: This problem requires understanding the questions of representation.

****************
A pattern matcher:    13 points
A pattern is an expression containing variables which may  take on "values" which are
subexpressions. For example, consider the expression
   e = (TIMES (PLUS 3 X) (PLUS 7 2) 3)
and the pattern
   p = (TIMES (PLUS VAR1 X) VAR2 VAR1).

This pattern, p, matches the  expression if VAR1 and VAR2 are bound to  3 and (PLUS 7 2)
respectively.    Define  a  function,  inst[e;p;m]  whose  value  is  a  table  of
variable-bindings (a simple symbol table)  which when substituted into the  argument,
p,  yields the  expression e.  The argument,  m, is  an initial  table of  previously
committed  substitutions. inst is to return NO if  the pattern does not match, and ()
if the pattern (modified by  the initial value of m) is identical  to the expression.
Thus  using the  above  examples of  p and  e,  inst[e;p;()] should  return something
representing  {<VAR1:3>, <VAR2:(PLUS  7  2)>}.   But  (again  using  p and  e  above)
inst[e;p; {<VAR1:4>}] returns NO.  As usual make the function as abstract as posible,
separating out  the representational  details to  subfunctions. In  dealing with  the
represntation, you may assume  whatever naming scheme you wish for  the VARs. You may
assume that no VARs occur in the expression, e. In fact, if VARs DO occur, you have a
another headache!  Those of you who are masochistic might examine that problem. 

************
Write an algebraic simplifier:   13 points
As we saw in  the differentiation example (p. 39  - Stupor LISP) the results  of such
manipulation  in  symbolic   mathematics  can  lead  to  very  poor  representations.
Sophisticated algebraic simplifiers are a necessity.  Begin the construction  of such
a simplifier, keeping its structure as  separate as possible from the representation.
You  may restrict attention  to expressions involving variables,  integers, and sums,
products and powers  of such.  Show  your representation of the  simplification rules
and take care to allow easy addition of new rules. 

Your rules should include such as x+0=>x, x*0=>0, x↑0=>1,... .

************
A quessing game:       5 points
what does this function do?

foo <= λ[[x] [atom[x] → x; T → cons[foo[car[x]];foo[cdr[x]]] ]

************
a problem and a question of efficiency:      11 points
Let l be a list  of length n: (l1, l2, l3,  ln). Each li is also a list  of length m.
Write  a function, aargh[l] which  is to return  that first sequence  (l1j, l2j, lnj)
whose elements are not all equal. 
For example:
	aargh[((A B C)(A C E)(A B E))] = (B C B)
	aargh[((A B C D)(A B E (1)))] = (C E)

Try to make an efficient computation. Explain the difficulties involved.

*************
And still it comes: additions to the evalautor      10 points
Write modifications to the value[e;tbl] function  which will  handle sums of  arbitrary
length. Do it two ways: with and without functional arguments. 

**************
equality on data structures         23 points
Recall that  a sequence (x1,  x2, x3, xn)  was defined as  having a  specific imposed
order: (A,  B) ≠ (B, A); and  two sequences are equal if  they are element-wise equal
and have the same length: (A, B, C) ≠ (A, B). 

A set {x1, x2,  x3, xn} on the other  hand, is defined as an  unordered collection of
elements; reptitions are not included:
    {1,2,A} = {A,2,1} = {A,2,A,1,1}

A data structure intermediate in complexity (between sets  and sequences) is a "bag".
A bag <x1, x2,  x3, xn>, has no imposed order, but may have repeated elements: 
<1, 2, 2> = <2, 1, 2> but does not equal <1, 2>. 

Notice that one  application of sequences is  the parameter-list to a  function call:
f[a1,a2, ...an].  The order of the ai's is important  and there can be repetitions (a
sequence).  FIRST QUESTION:  bags are a useful notation  for the parameter-list of  a
certain class of functions. what is this class ( 2 points). 

Pick representations for  each of these three  data structures. Write versions  of an
equality predicate which will implement the desired equality. 

equal_seq[(E,A,A,D,B,C);(A,B,D,E)] = NIL
equal_set[{E,A,A,D,B,C};{A,C,B,D,E}] = T
equal_bag[<E,A,D,A,C>;<A,C,A,D,E>] = T

points: 3 for sequences, 9 for sets, and 9 for bags.